from vec2 import Vec2

class QuadTreeNode():

    def __init__(self):
        self.gList      = []
        self.center     = Vec2()
        self.width      = 0.0
        self.halfW      = 0.0
        self.fourW      = 0.0
        self.maxX       = 0.0
        self.maxY       = 0.0
        self.minX       = 0.0
        self.minY       = 0.0
        self.parent     = None
        self.children   = []
        self.nodeCursor = 0

class QuadTree():
    
    def __init__(self):
        self.root      = None
        self.gLocation = {}

    def resize(self, width, x, y, resolution):
        self.root = self.buildNode(width, x, y, None)
        cursor    = self.root
        
        while( not(cursor == None) ):
            if( (cursor.width <= resolution) or (cursor.nodeCursor == 4) ):
                cursor = cursor.parent
            else:
                if(cursor.nodeCursor == 0):
                    c = self.buildNode(cursor.halfW, cursor.center.x + cursor.fourW, cursor.center.y + cursor.fourW, cursor)
                elif(cursor.nodeCursor == 1):
                    c = self.buildNode(cursor.halfW, cursor.center.x + cursor.fourW, cursor.center.y - cursor.fourW, cursor)
                elif(cursor.nodeCursor == 2):
                    c = self.buildNode(cursor.halfW, cursor.center.x - cursor.fourW, cursor.center.y + cursor.fourW, cursor)
                elif(cursor.nodeCursor == 3):
                    c = self.buildNode(cursor.halfW, cursor.center.x - cursor.fourW, cursor.center.y - cursor.fourW, cursor)
                cursor.nodeCursor += 1
                cursor.children.append(c)
                cursor = c
                
    def clear(self):
        keys = []
        for c in self.gLocation.iterkeys():
            keys.append(c)
        for c in keys:
            self.remove(c)
        self.gLocation = {}
        
    def buildNode(self, width, x, y, parent):
        node = QuadTreeNode()

        node.width = width
        node.halfW = width / 2.0
        node.fourW = width / 4.0

        node.center.x = x
        node.center.y = y

        node.maxX = node.center.x + node.halfW
        node.maxY = node.center.y + node.halfW
        node.minX = node.center.x - node.halfW
        node.minY = node.center.y - node.halfW
        
        node.parent = parent

        return node
    
    def insert(self, geometry):
        cursor    = self.root
        child     = None
        notPlaced = True
        
        if(geometry.hasVar("pos") and geometry.hasVar("xMax") and geometry.hasVar("yMax") and geometry.hasVar("xMin") and geometry.hasVar("yMin")):
            p = geometry.getVar("pos")
            maxX = geometry.getVar("xMax")
            maxY = geometry.getVar("yMax")
            minX = geometry.getVar("xMin")
            minY = geometry.getVar("yMin")      
                        
            while(notPlaced):
                notPlaced = False
            
                if(len(cursor.children) > 0):
                    if(p.x < cursor.center.x):
                        if(p.y < cursor.center.y):
                            child = cursor.children[3]
                        else:
                            child = cursor.children[2]
                    else:
                        if(p.y < cursor.center.y):
                            child = cursor.children[1]
                        else:
                            child = cursor.children[0]
                            
                    if(maxX < child.maxX):
                        if(maxY < child.maxY):
                            if(minX > child.minX):
                                if(minY > child.minY):
                                    cursor = child
                                    notPlaced = True
                                
            cursor.gList.append(geometry)
            self.gLocation[geometry] = cursor.gList
        
    def remove(self, geometry):
        if(self.gLocation.has_key(geometry)):
            v = self.gLocation.pop(geometry)
            v.remove(geometry)
            
    def overlaps(self, node, geometry):
        overlap = False
    
        if(geometry.hasVar("pos") and geometry.hasVar("xMax") and geometry.hasVar("yMax") and geometry.hasVar("xMin") and geometry.hasVar("yMin")):
            p = geometry.getVar("pos")
            maxX = geometry.getVar("xMax")
            maxY = geometry.getVar("yMax")
            minX = geometry.getVar("xMin")
            minY = geometry.getVar("yMin")
        
            xDist  = abs(node.center.x - p.x)
            yDist  = abs(node.center.y - p.y)
            width  = ((maxX - minX) / 2.0) + node.halfW
            height = ((maxY - minY) / 2.0) + node.halfW
        
            if( (width > xDist) and (height > yDist) ):
                overlap = True
            
        return overlap
  
    def detectCollisions(self, geometry):
        cursor = self.root
        cursor.nodeCursor = 0
        child  = None
        
        while( not(cursor == None) ):
            if( (len(cursor.children) > 0) and (cursor.nodeCursor < 4) ):
                child = cursor.children[cursor.nodeCursor]
                cursor.nodeCursor += 1
                if(self.overlaps(child, geometry)):
                    cursor = child
                    cursor.nodeCursor = 0
            else:
                for c in cursor.gList:
                    t, d1, d2, v1, v2, s1, s2 = geometry.checkCollision(c)
                    if(t):
                        if(geometry.hasVar("collisions")):
                            geometry.getVar("collisions").append([d1, v1, s1, c])
                        if(c.hasVar("collisions")):
                            c.getVar("collisions").append([d2, v2, s2, geometry])
                cursor = cursor.parent
    